Search results for "graph homomorphism"
showing 3 items of 3 documents
An exact method for graph coloring
2006
International audience; We are interested in the graph coloring problem. We propose an exact method based on a linear-decomposition of the graph. The complexity of this method is exponential according to the linearwidth of the entry graph, but linear according to its number of vertices. We present some experiments performed on literature instances, among which COLOR02 library instances. Our method is useful to solve more quickly than other exact algorithms instances with small linearwidth, such as mug graphs. Moreover, our algorithms are the first to our knowledge to solve the COLOR02 instance 4-Inser_3 with an exact method.
About Graph Mappings
2019
Summary In this articles adjacency-preserving mappings from a graph to another are formalized in the Mizar system [7], [2]. The generality of the approach seems to be largely unpreceeded in the literature to the best of the author’s knowledge. However, the most important property defined in the article is that of two graphs being isomorphic, which has been extensively studied. Another graph decorator is introduced as well.
About Vertex Mappings
2019
Summary In [6] partial graph mappings were formalized in the Mizar system [3]. Such mappings map some vertices and edges of a graph to another while preserving adjacency. While this general approach is appropriate for the general form of (multidi)graphs as introduced in [7], a more specialized version for graphs without parallel edges seems convenient. As such, partial vertex mappings preserving adjacency between the mapped verticed are formalized here.